import java.util.ArrayList;
import java.util.List;

/**
 * @program: leetcode046
 * @author: JCM
 * @create: 2022-11-29 08:42
 * @description: 全排列
 **/
public class LeetCode046 {
    public static int[] book = new int[10];
    public static List<List<Integer>> ret = new ArrayList<>();
    public static int[] a = new int[10];
    public static void main(String[] args) {
        int[] nums = {1,2,3};
        List<List<Integer>> ans = permute(nums);
        System.out.println(ans.toString());
    }
    private static List<List<Integer>> permute(int[] nums) {
        for(int i = 0;i < nums.length; i++) {
            book[i] = 0;
        }
        dfs(nums,0);
        return ret;
    }
    private static void dfs(int[] nums, int step) {
        if(step == nums.length) {
            List<Integer> list = new ArrayList<>();
            for(int i = 0; i < step; i++) {
                list.add(a[i]);
            }
            ret.add(list);
            return;
        }

        for(int i = 0; i < nums.length; i++) {
            if(book[i] == 0) {
                a[step] = nums[i];
                book[i] = 1;
                dfs(nums,step+1);
                book[i] = 0;
            }
        }
        return;
    }
}
